package com.sheng.leetcode.year2022.month05.day23;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author liusheng
 * @date 2022/05/23
 *
 * 675. 为高尔夫比赛砍树
 *
 * 你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
 * 0 表示障碍，无法触碰
 * 1 表示地面，可以行走
 * 比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
 * 每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
 * 你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
 * 你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
 * 可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
 *
 * 示例 1：
 *
 * 输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
 * 输出：6
 * 解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。
 * 示例 2：
 *
 * 输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
 * 输出：-1
 * 解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。
 * 示例 3：
 *
 * 输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
 * 输出：6
 * 解释：可以按与示例 1 相同的路径来砍掉所有的树。
 * (0,0) 位置的树，可以直接砍去，不用算步数。
 *
 * 提示：
 *
 * m == forest.length
 * n == forest[i].length
 * 1 <= m, n <= 50
 * 0 <= forest[i][j] <= 109
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/cut-off-trees-for-golf-event
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0675 {

    @Test
    public void test01(){
        int[][] ints = {{1,2,3},{0,0,4},{7,6,5}};
//        int[][] ints = {{1,2,3},{0,0,0},{7,6,5}};
//        int[][] ints = {{2,3,4},{0,0,5},{8,7,6}};
        //二维数组转换成集合
        List<List<Integer>> forest = Arrays.stream(ints).map(i -> {
            return Arrays.stream(i).boxed().collect(Collectors.toList());
        }).collect(Collectors.toList());
        System.out.println(new Solution().cutOffTree(forest));
    }

}
//class Solution {
//    public int cutOffTree(List<List<Integer>> forest) {
//        //从低到高砍掉所有的树
//        return 0;
//    }
//}

//https://www.pudn.com/news/628e43e6e014212d4a89438d.html

//首先将矩阵中的树从小到大排序（数组中存的是每一棵树的位置）
//通过bfs找到从某一个位置到另一个位置的最短路径（求最少移动步数，一般可以使用 BFS 去做）
//最后求和所有的最短路径

class Solution {
    public int cutOffTree(List<List<Integer>> forest) {

        List<int[]> list = new ArrayList<>();
        getAllWithSort(forest, list);
        int res = 0;
        int x = 0;
        int y = 0;
        for (int i = 0; i < list.size(); i++) {

            int step = process(forest, x, y, list.get(i)[0], list.get(i)[1]);
            if (step == -1) {
                return -1;
            }
            res += step;
            x = list.get(i)[0];
            y = list.get(i)[1];
        }

        return res;

    }

    // bfs
    int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};;
    private int process(List<List<Integer>> forest, int startX, int startY, Integer targetX, Integer targetY) {

        int N = forest.size();
        int M = forest.get(0).size();

        boolean[][] visited = new boolean[N][M];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {startX, startY});
        visited[startX][startY] = true;
        int step = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] poll = queue.poll();
                if (poll[0] == targetX && poll[1] == targetY) {
                    return step;
                }
                for (int i = 0; i < 4; i++) {
                    int curX = poll[0] + directions[i][0];
                    int curY = poll[1] + directions[i][1];

                    if (curX >=0 && curY >= 0 && curX < N && curY < M && forest.get(curX).get(curY) != 0 && !visited[curX][curY]) {
                        queue.add(new int[] {curX, curY});
                        visited[curX][curY] = true;
                    }

                }
            }
            step++;
        }
        return -1;
    }

    // 1 是地面，不用砍树，直接行走。
    // forest 表示所有的树   list 表示返回的排序的树的位置
    private void getAllWithSort(List<List<Integer>> forest, List<int[]> list) {

        int N = forest.size();
        int M = forest.get(0).size();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (forest.get(i).get(j) > 1) {
                    list.add(new int[] {i, j});
                }
            }
        }
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return forest.get(o1[0]).get(o1[1]) - forest.get(o2[0]).get(o2[1]);
            }
        });
    }
}
